<!DOCTYPE html>



  


<html class="theme-next pisces use-motion" lang="zh-Hans">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">






  
  
  <link rel="stylesheet" media="all" href="/lib/Han/dist/han.min.css?v=3.3">




<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.3" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.3">


  <link rel="icon" type="image/png" sizes="32x32" href="/img/icon.png?v=5.1.3">


  <link rel="icon" type="image/png" sizes="16x16" href="/img/icon.png?v=5.1.3">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.3" color="#222">





  <meta name="keywords" content="cayun's blog, IT, ACM/ICPC, blog, cayun" />










<meta property="og:type" content="website">
<meta property="og:title" content="cayun&#39;s blog">
<meta property="og:url" content="http://localhost/page/5/index.html">
<meta property="og:site_name" content="cayun&#39;s blog">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="cayun&#39;s blog">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Pisces',
    version: '5.1.3',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://localhost/page/5/"/>





  <title>cayun's blog</title>
  




<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
            (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
          m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
  ga('create', 'UA-93052608-1', 'auto');
  ga('send', 'pageview');
</script>


  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?1ca7c9c8011b37b0c209724dc77c24db";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left 
  page-home">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">cayun's blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <h1 class="site-subtitle" itemprop="description">不积跬步, 无以至千里!</h1>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/gym101158D/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/gym101158D/" itemprop="url">Gym 101158D Hidden Anagrams (Hash)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-07-06T00:00:00+08:00">
                2017-07-06
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/gym101158D/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/gym101158D/" class="cy_cmt_count" data-xid="gym101158D/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>因为这一题我们比较字符串时是乱序的，于是我们可以想到构造一个不考虑顺序的哈希函数，这个不难想，最朴素的想法就是假设每个字母各自对应一个不同的值，然后相加就可以了。接下来我们可以先对是s1串预处理出每个区间的哈希值，时间为$O(n^2)$。然后再处理s2串，和之前一样的处理方式，这个时候每次求得一个区间的哈希值之后，再判定s1中存不存满足哈希值相等且区间长度相同的。但是由于哈希值会有冲突，所以光判定这些还不够，我们再记录前缀和数组，判断s1区间和s2区间中每个字母的数量是否相同就行了。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</div><div class="line"><span class="keyword">typedef</span> pair&lt;<span class="keyword">int</span>, <span class="keyword">int</span>&gt; PII;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">4005</span>;</div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> HASH = <span class="number">4777777</span>;</div><div class="line"><span class="keyword">int</span> n, m;</div><div class="line"><span class="keyword">int</span> numa[N][<span class="number">128</span>], numb[N][<span class="number">128</span>];</div><div class="line">LL hashMap[<span class="number">128</span>];</div><div class="line"><span class="keyword">char</span> s1[N], s2[N];</div><div class="line"></div><div class="line"><span class="built_in">vector</span>&lt;PII&gt; hash[HASH];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">bool</span> <span class="title">isOk</span><span class="params">(<span class="keyword">int</span> l1, <span class="keyword">int</span> r1, <span class="keyword">int</span> l2, <span class="keyword">int</span> r2)</span> </span>&#123;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> c = <span class="string">'a'</span>; c &lt;= <span class="string">'z'</span>; c++) &#123;</div><div class="line">        <span class="keyword">if</span> (numa[r1][c] - numa[l1<span class="number">-1</span>][c] != numb[r2][c] - numb[l2<span class="number">-1</span>][c]) <span class="keyword">return</span> <span class="literal">false</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="string">'a'</span>; i &lt;= <span class="string">'z'</span>; i++) </div><div class="line">        hashMap[i] = (LL)i * i * i * i + <span class="number">17L</span>L;</div><div class="line">    <span class="built_in">scanf</span>(<span class="string">"%s%s"</span>, s1 + <span class="number">1</span>, s2 + <span class="number">1</span>);</div><div class="line">    n = <span class="built_in">strlen</span>(s1 + <span class="number">1</span>), m = <span class="built_in">strlen</span>(s2 + <span class="number">1</span>);</div><div class="line">    <span class="built_in">memset</span>(numa, <span class="number">0</span>, <span class="keyword">sizeof</span> numa);</div><div class="line">    <span class="built_in">memset</span>(numb, <span class="number">0</span>, <span class="keyword">sizeof</span> numb);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="string">'a'</span>; j &lt;= <span class="string">'z'</span>; j++) </div><div class="line">            numa[i][j] = numa[i<span class="number">-1</span>][j];</div><div class="line">        numa[i][s1[i]]++;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= m; i++) &#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="string">'a'</span>; j &lt;= <span class="string">'z'</span>; j++)</div><div class="line">            numb[i][j] = numb[i<span class="number">-1</span>][j];</div><div class="line">        numb[i][s2[i]]++;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    LL ans = <span class="number">0</span>;</div><div class="line"></div><div class="line">    LL tmp = <span class="number">0</span>, t;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        tmp += hashMap[s1[i]];</div><div class="line">        t = tmp;</div><div class="line">        hash[t % HASH].push_back(PII(<span class="number">1</span>, i));</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">2</span>; j &lt;= i; j++) &#123;</div><div class="line">            t -= hashMap[s1[j<span class="number">-1</span>]];</div><div class="line">            hash[t % HASH].push_back(PII(j, i));</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    tmp = <span class="number">0</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= m; i++) &#123;</div><div class="line">        tmp += hashMap[s2[i]];</div><div class="line">        t = tmp;</div><div class="line">        LL hashValue = t % HASH;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> k = <span class="number">0</span>; k &lt; hash[hashValue].size(); k++) &#123;</div><div class="line">            <span class="keyword">int</span> l = hash[hashValue][k].first;</div><div class="line">            <span class="keyword">int</span> r = hash[hashValue][k].second;</div><div class="line">            <span class="keyword">if</span> (r - l == i - <span class="number">1</span>) &#123;</div><div class="line">                <span class="keyword">if</span> (i &gt; ans &amp;&amp; isOk(l, r, <span class="number">1</span>, i)) &#123;</div><div class="line">                    ans = i;</div><div class="line">                    <span class="keyword">break</span>;</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">2</span>; j &lt;= i; j++) &#123;</div><div class="line">            <span class="keyword">if</span> (i - j + <span class="number">1</span> &lt;= ans) <span class="keyword">break</span>;</div><div class="line">            t -= hashMap[s2[j<span class="number">-1</span>]];</div><div class="line">            hashValue = t % HASH;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> k = <span class="number">0</span>; k &lt; hash[hashValue].size(); k++) &#123;</div><div class="line">                <span class="keyword">int</span> l = hash[hashValue][k].first;</div><div class="line">                <span class="keyword">int</span> r = hash[hashValue][k].second;</div><div class="line">                <span class="keyword">if</span> (r - l == i - j) &#123;</div><div class="line">                    <span class="keyword">if</span> (isOk(l, r, j, i)) ans = i - j + <span class="number">1</span>;</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, ans);</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/gym101158C/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/gym101158C/" itemprop="url">Gym 101158C Distribution Center (模拟)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-07-06T00:00:00+08:00">
                2017-07-06
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/gym101158C/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/gym101158C/" class="cy_cmt_count" data-xid="gym101158C/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>就是求 对于每条线，紧挨着这条线之前的连续的最长上升序列的长度+紧挨着这条线之后的连续的最长下降序列的长度+$1$</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">200010</span>;</div><div class="line"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; g[N], up[N], down[N];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> n, m; <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;n, &amp;m);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; m; i++) &#123;</div><div class="line">        <span class="keyword">int</span> x, y; <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;x, &amp;y);</div><div class="line">        g[y].push_back(x);</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++)</div><div class="line">        sort(g[i].begin(), g[i].end());</div><div class="line"></div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        <span class="keyword">int</span> k = <span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; g[i].size(); j++) &#123;</div><div class="line">            <span class="keyword">while</span> (k &lt; <span class="number">0</span> || (k &lt; g[i<span class="number">-1</span>].size() &amp;&amp; g[i<span class="number">-1</span>][k] &lt; g[i][j])) k++;</div><div class="line">            k--;</div><div class="line">            <span class="keyword">if</span> (k &lt; <span class="number">0</span>) up[i].push_back(<span class="number">1</span>);</div><div class="line">            <span class="keyword">else</span> up[i].push_back(up[i<span class="number">-1</span>][k] + <span class="number">1</span>);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = n; i &gt;= <span class="number">1</span>; i--) &#123;</div><div class="line">        <span class="keyword">int</span> k = <span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; g[i].size(); j++) &#123;</div><div class="line">            <span class="keyword">while</span> (k &lt; <span class="number">0</span> || (k &lt; g[i+<span class="number">1</span>].size() &amp;&amp; g[i+<span class="number">1</span>][k] &lt; g[i][j])) k++;</div><div class="line">            k--;</div><div class="line">            <span class="keyword">if</span> (k &lt; <span class="number">0</span>) down[i].push_back(<span class="number">1</span>);</div><div class="line">            <span class="keyword">else</span> down[i].push_back(down[i+<span class="number">1</span>][k] + <span class="number">1</span>);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        <span class="keyword">int</span> mxup = <span class="number">0</span>, mxdown = <span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; g[i<span class="number">-1</span>].size(); j++) &#123;</div><div class="line">            mxup = max(mxup, up[i<span class="number">-1</span>][j]);</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; g[i].size(); j++) &#123;</div><div class="line">            mxdown = max(mxdown, down[i][j]);</div><div class="line">        &#125;</div><div class="line">        <span class="comment">//printf("\nmxup=%d, mxdown=%d\n", mxup, mxdown);</span></div><div class="line">        <span class="built_in">printf</span>(<span class="string">"%d%c"</span>, mxup + mxdown + <span class="number">1</span>, i == n ? <span class="string">'\n'</span> : <span class="string">' '</span>);</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/gym101158G/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/gym101158G/" itemprop="url">Gym 101158G Placing Medals on a Binary Tree (Hash)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-07-06T00:00:00+08:00">
                2017-07-06
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/gym101158G/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/gym101158G/" class="cy_cmt_count" data-xid="gym101158G/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>其实这一题稍微思考一下可以想到那个吃蛋糕每次吃一半的故事。那么这一题最朴素的想法很显然也就是这个样子。对于第一层占$\frac{1}{2}$，第二层占$\frac{1}{4}$，第三层占$\frac{1}{8}$，那么对于每次加进来我们只需要判断当前的剩余的蛋糕够不够吃就行。但是如果是这样考虑的话，就会出现一个问题，那就是浮点数精度的问题。于是我们可以换个方向，因为每层的占比大小都是后一层的两倍，那么我们可以考虑一个数组来记录每一层已经吃掉的次数，那么若对于某一层吃掉了$2$个的话，我们就可以将这一层并到前一层，如此并下去，直到该层的次数小于$2$，或者该层已经是第$0$层。若不是第$0$层，说明答案就是Yes，否则判断一下是否刚好占比为$1$，若刚好为$1$，那还是Yes，若不刚好，那即为No。合并失败的话，我们再将情况复原即可。由于x的范围太大，我们可以想到使用离散化来解决，但是STL的map时间复杂度为$O(logn)$无法满足我们的时间需要，这个时候我们自己手写一个HashMap即可。需要注意的是，这道题目有个很重要的剪枝，那就是若之前假设在$i$深度节点已经无法放置奖牌了，那么对于之后所有的$j &lt;= i$一定也无法放置奖牌。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">typedef</span> pair&lt;<span class="keyword">int</span>, <span class="keyword">int</span>&gt; PII;</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">HashMap</span> &#123;</span></div><div class="line">    <span class="keyword">enum</span> &#123;HASH_LENGTH = <span class="number">977777</span>&#125;;</div><div class="line">    PII hash[HASH_LENGTH];</div><div class="line">    <span class="keyword">bool</span> vis[HASH_LENGTH];</div><div class="line"></div><div class="line">    HashMap() &#123;</div><div class="line">        <span class="built_in">memset</span>(vis, <span class="literal">false</span>, <span class="keyword">sizeof</span> vis);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">hashPosition</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</div><div class="line">        <span class="keyword">return</span> x % HASH_LENGTH;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">getPosition</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</div><div class="line">        <span class="keyword">int</span> p = hashPosition(x);</div><div class="line">        <span class="keyword">while</span> (vis[p] &amp;&amp; hash[p].first != x) &#123;</div><div class="line">            p++;</div><div class="line">            <span class="keyword">if</span> (p == HASH_LENGTH) p = <span class="number">0</span>;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">return</span> p;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">get</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</div><div class="line">        <span class="keyword">int</span> p = getPosition(x);</div><div class="line">        <span class="keyword">return</span> vis[p] ? hash[p].second : <span class="number">0</span>;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">insert</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y)</span> </span>&#123;</div><div class="line">        <span class="keyword">int</span> p = getPosition(x);</div><div class="line">        <span class="keyword">if</span> (vis[p]) &#123;</div><div class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</div><div class="line">        &#125; <span class="keyword">else</span> &#123;</div><div class="line">            vis[p] = <span class="literal">true</span>;</div><div class="line">            hash[p] = make_pair(x, y);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y)</span> </span>&#123;</div><div class="line">        <span class="keyword">int</span> p = getPosition(x);</div><div class="line">        <span class="keyword">if</span> (!vis[p]) &#123;</div><div class="line">            vis[p] = <span class="literal">true</span>;</div><div class="line">            hash[p] = make_pair(x, y);</div><div class="line">        &#125; <span class="keyword">else</span> &#123;</div><div class="line">            hash[p].second += y;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">set</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y)</span> </span>&#123;</div><div class="line">        <span class="keyword">int</span> p = getPosition(x);</div><div class="line">        <span class="keyword">if</span> (!vis[p]) &#123;</div><div class="line">            vis[p] = <span class="literal">true</span>;</div><div class="line">            hash[p] = make_pair(x, y);</div><div class="line">        &#125; <span class="keyword">else</span> &#123;</div><div class="line">            hash[p].second = y;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line">HashMap mm;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> n; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;n);</div><div class="line">    <span class="keyword">int</span> mx = <span class="number">0</span>;</div><div class="line">    <span class="keyword">int</span> mn = <span class="number">0</span>;</div><div class="line">    <span class="keyword">while</span> (n--) &#123;</div><div class="line">        <span class="keyword">int</span> x; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;x);</div><div class="line">        <span class="keyword">int</span> tx = x;</div><div class="line">        <span class="keyword">if</span> (mn &gt;= x || mm.get(<span class="number">0</span>) &gt; <span class="number">0</span>) &#123;</div><div class="line">            <span class="built_in">puts</span>(<span class="string">"No"</span>);</div><div class="line">        &#125; <span class="keyword">else</span> &#123;</div><div class="line">            mm.add(tx, <span class="number">1</span>);</div><div class="line">            <span class="keyword">while</span> (tx &gt; <span class="number">0</span> &amp;&amp; mm.get(tx) == <span class="number">2</span>) &#123;</div><div class="line">                mm.<span class="built_in">set</span>(tx, <span class="number">0</span>);</div><div class="line">                tx--;</div><div class="line">                mm.add(tx, <span class="number">1</span>);</div><div class="line">            &#125;</div><div class="line">            <span class="keyword">if</span> (tx == <span class="number">0</span> &amp;&amp; mx &lt;= x) &#123;</div><div class="line">                <span class="built_in">puts</span>(<span class="string">"Yes"</span>);</div><div class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (tx == <span class="number">0</span>) &#123;</div><div class="line">                <span class="built_in">puts</span>(<span class="string">"No"</span>);</div><div class="line">                mn = max(mn, x);</div><div class="line">                mm.<span class="built_in">set</span>(<span class="number">0</span>, <span class="number">0</span>);</div><div class="line">                <span class="keyword">while</span> (tx &lt; x) &#123;</div><div class="line">                    tx++;</div><div class="line">                    mm.<span class="built_in">set</span>(tx, <span class="number">1</span>);</div><div class="line">                &#125;</div><div class="line">            &#125; <span class="keyword">else</span> &#123;</div><div class="line">                <span class="built_in">puts</span>(<span class="string">"Yes"</span>);</div><div class="line">                <span class="keyword">if</span> (mx &lt;= x) mx = tx;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/codeforces822C/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/codeforces822C/" itemprop="url">codeforces 822C Hacker, pack your bags! (二分+RMQ)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-07-06T00:00:00+08:00">
                2017-07-06
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/ACM-ICPC/" itemprop="url" rel="index">
                    <span itemprop="name">ACM/ICPC</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/codeforces822C/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/codeforces822C/" class="cy_cmt_count" data-xid="codeforces822C/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>首先我们先对Voucher以长度为第一关键字，左端点为第二关键字排序。那么对于$v<em>{i}$，我们可以很容易通过二分找到一个区间，使得这个区间内的任一$v</em>{p}$的$v<em>{p}.l &gt; v</em>{i}.r$且$v<em>{p}.length + v</em>{i}.length = x$。这个时候为了加快运算速度，我们需要求取区间内的最小cost，这就是一个明显的RMQ问题，直接使用ST算法即可。</p>
          <!--noindex-->
          <div class="post-button text-center">
            <a class="btn" href="/codeforces822C/" rel="contents">
              阅读全文 &raquo;
            </a>
          </div>
          <!--/noindex-->
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/gym101164I/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/gym101164I/" itemprop="url">Gym 101164I Cubes (搜索+剪枝)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-07-04T00:00:00+08:00">
                2017-07-04
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/gym101164I/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/gym101164I/" class="cy_cmt_count" data-xid="gym101164I/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>题解摘自<a href="http://www.cnblogs.com/flipped/p/6404698.html" target="_blank" rel="external">http://www.cnblogs.com/flipped/p/6404698.html</a><br>根据n的范围，立方数最大不超过$400$的立方，并且个数也不会很多。<br>dfs，设置一个深度的上限up。从大到小枚举立方数，剪枝条件：当前层数加上至少还需要的层数&gt;=up就return。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">400</span>;</div><div class="line"><span class="keyword">int</span> tri[N], ans[N], p[N];</div><div class="line"><span class="keyword">int</span> tn = <span class="number">0</span>, an = <span class="number">40</span>, pn;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> num, <span class="keyword">int</span> x, <span class="keyword">int</span> m)</span> </span>&#123;</div><div class="line">    <span class="keyword">if</span> (x == <span class="number">0</span>) &#123;</div><div class="line">        <span class="keyword">if</span> (num &lt;= an) &#123;</div><div class="line">            an = num;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; an; i++) ans[i] = p[i];</div><div class="line">        &#125;</div><div class="line">    &#125; <span class="keyword">else</span> &#123;</div><div class="line">        <span class="keyword">while</span> (x &lt; tri[m]) m--;</div><div class="line">        <span class="keyword">if</span> (num + <span class="number">1</span> &gt;= an || num + x / tri[m] &gt;= an) <span class="keyword">return</span>;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = m; i &gt; <span class="number">0</span>; i--) &#123;       </div><div class="line">            p[num] = i;</div><div class="line">            dfs(num + <span class="number">1</span>, x - tri[i], i);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> n; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;n);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i * i * i &lt;= <span class="number">44777444</span>; i++) tri[++tn] = i * i * i;</div><div class="line">    dfs(<span class="number">0</span>, n, tn);</div><div class="line">    <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, an);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; an; i++) <span class="built_in">printf</span>(<span class="string">"%d%c"</span>, ans[i], i == an - <span class="number">1</span> ? <span class="string">'\n'</span> : <span class="string">' '</span>);</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/gym101164H/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/gym101164H/" itemprop="url">Gym 101164H Pub crawl (凸包)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-07-04T00:00:00+08:00">
                2017-07-04
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/gym101164H/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/gym101164H/" class="cy_cmt_count" data-xid="gym101164H/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>其实这一题就是做一个无限求下去直到所有点都包含了的凸包，原因很简单，因为不存在三点共线，所以最后一定能将每个点都包含进来。至于无限求下去的凸包，就是记录一下点是否已经包含在凸包内，不重复访问就行，直接修改凸包模板即可。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Pnt</span> &#123;</span></div><div class="line">    LL x, y;</div><div class="line">    <span class="keyword">int</span> id;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">read</span><span class="params">()</span> </span>&#123;</div><div class="line">        <span class="built_in">scanf</span>(<span class="string">"%lld%lld"</span>, &amp;x, &amp;y);</div><div class="line">    &#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">bool</span> <span class="title">cmpXY</span><span class="params">(<span class="keyword">const</span> Pnt &amp;a, <span class="keyword">const</span> Pnt &amp;b)</span> </span>&#123;</div><div class="line">    <span class="keyword">return</span> a.x == b.x ? a.y &lt; b.y : a.x &lt; b.x;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function">LL <span class="title">Cross</span><span class="params">(<span class="keyword">const</span> Pnt &amp;o, <span class="keyword">const</span> Pnt &amp;a, <span class="keyword">const</span> Pnt &amp;b)</span> </span>&#123;</div><div class="line">    LL dx1 = a.x - o.x, dy1 = a.y - o.y;</div><div class="line">    LL dx2 = b.x - o.x, dy2 = b.y - o.y;</div><div class="line">    <span class="keyword">return</span> dx1 * dy2 - dx2 * dy1;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">5005</span>;</div><div class="line">Pnt a[N], stk[N];</div><div class="line"><span class="keyword">int</span> ans[N];</div><div class="line"><span class="keyword">bool</span> vis[N];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">Convex</span><span class="params">(Pnt a[], <span class="keyword">int</span> n)</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> m = <span class="number">0</span>;</div><div class="line">    <span class="keyword">while</span> (<span class="literal">true</span>) &#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</div><div class="line">            <span class="keyword">if</span> (vis[a[i].id]) <span class="keyword">continue</span>;</div><div class="line">            <span class="keyword">while</span> (m &gt; <span class="number">1</span> &amp;&amp; Cross(stk[m - <span class="number">2</span>], stk[m - <span class="number">1</span>], a[i]) &lt;= <span class="number">0</span>) &#123;</div><div class="line">                m--;</div><div class="line">                vis[stk[m].id] = <span class="literal">false</span>;</div><div class="line">            &#125;</div><div class="line">            stk[m++] = a[i];</div><div class="line">            vis[a[i].id] = <span class="literal">true</span>;</div><div class="line">            <span class="keyword">if</span> (m == n) <span class="keyword">return</span>;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">int</span> mm = m;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = n - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i--) &#123;</div><div class="line">            <span class="keyword">if</span> (vis[a[i].id]) <span class="keyword">continue</span>;</div><div class="line">            <span class="keyword">while</span> (m &gt; mm &amp;&amp; Cross(stk[m - <span class="number">2</span>], stk[m - <span class="number">1</span>], a[i]) &lt;= <span class="number">0</span>) &#123;</div><div class="line">                m--;</div><div class="line">                vis[stk[m].id] = <span class="literal">false</span>;</div><div class="line">            &#125;</div><div class="line">            stk[m++] = a[i];</div><div class="line">            vis[a[i].id] = <span class="literal">true</span>;</div><div class="line">            <span class="keyword">if</span> (m == n) <span class="keyword">return</span>;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> n;</div><div class="line">    <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;n);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</div><div class="line">        a[i].id = i + <span class="number">1</span>;</div><div class="line">        a[i].read();</div><div class="line">    &#125;</div><div class="line">    sort(a, a + n, cmpXY);</div><div class="line">    <span class="built_in">memset</span>(vis, <span class="literal">false</span>, <span class="keyword">sizeof</span>(vis));</div><div class="line">    Convex(a, n);</div><div class="line">    <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, n);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</div><div class="line">        <span class="built_in">printf</span>(<span class="string">"%d%c"</span>, stk[i].id, i == n - <span class="number">1</span> ? <span class="string">'\n'</span> : <span class="string">' '</span>);</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/gym101164C/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/gym101164C/" itemprop="url">Gym 101164C Castle (KMP)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-07-04T00:00:00+08:00">
                2017-07-04
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/gym101164C/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/gym101164C/" class="cy_cmt_count" data-xid="gym101164C/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>直到现在才发现原来KMP的原理是这样的，关于KMP的原理，详见<a href="http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html" target="_blank" rel="external">阮一峰的博客</a>。<br>然后稍微想一下就能知道这一题的解法。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">1300000</span>;</div><div class="line"><span class="keyword">char</span> s[N];</div><div class="line"><span class="keyword">int</span> fail[N], ans[N];</div><div class="line"><span class="keyword">bool</span> vis[N];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> n, e; <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;n, &amp;e);</div><div class="line">    <span class="built_in">scanf</span>(<span class="string">"%s"</span>, s + <span class="number">1</span>);</div><div class="line">    <span class="keyword">int</span> j = <span class="number">0</span>; fail[<span class="number">1</span>] = <span class="number">0</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">2</span>; i &lt;= n; i++) &#123;</div><div class="line">        <span class="keyword">while</span> (j &gt; <span class="number">0</span> &amp;&amp; s[j+<span class="number">1</span>] != s[i]) j = fail[j];</div><div class="line">        <span class="keyword">if</span> (s[j+<span class="number">1</span>] == s[i]) j++;</div><div class="line">        fail[i] = j;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="built_in">memset</span>(ans, <span class="number">0</span>, <span class="keyword">sizeof</span>(ans));</div><div class="line">    <span class="built_in">memset</span>(vis, <span class="literal">false</span>, <span class="keyword">sizeof</span>(vis));</div><div class="line">    <span class="keyword">while</span> (e--) &#123;</div><div class="line">        <span class="keyword">int</span> op; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;op);</div><div class="line">        <span class="keyword">if</span> (op == <span class="number">1</span>) &#123;</div><div class="line">            <span class="keyword">char</span> c; <span class="built_in">scanf</span>(<span class="string">" %c"</span>, &amp;c);</div><div class="line">            s[++n] = c;</div><div class="line">            <span class="keyword">while</span> (j &gt; <span class="number">0</span> &amp;&amp; s[j+<span class="number">1</span>] != s[n]) j = fail[j];</div><div class="line">            <span class="keyword">if</span> (s[j+<span class="number">1</span>] == s[n]) j++;</div><div class="line">            fail[n] = j;</div><div class="line">            ans[n] = ans[j];</div><div class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (op == <span class="number">2</span>) &#123;</div><div class="line">            <span class="keyword">if</span> (!vis[n]) &#123;</div><div class="line">                ans[n]++;</div><div class="line">                vis[n] = <span class="literal">true</span>;</div><div class="line">            &#125;</div><div class="line">        &#125; <span class="keyword">else</span> &#123;</div><div class="line">            <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, ans[n]);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/gym101164D/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/gym101164D/" itemprop="url">Gym 101164D Reading Digits (暴力)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-07-04T00:00:00+08:00">
                2017-07-04
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/gym101164D/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/gym101164D/" class="cy_cmt_count" data-xid="gym101164D/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>设置一个a数组表示第$i$个数是什么，b数组表示$a_{i}$重复几次。即，将重复的进行合并。然后做$k$次暴力解密即可。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">500005</span>;</div><div class="line"><span class="keyword">char</span> s[N];</div><div class="line"><span class="keyword">int</span> a[<span class="number">2</span>][N];</div><div class="line"><span class="keyword">int</span> b[<span class="number">2</span>][N];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> k, pos;</div><div class="line">    <span class="built_in">scanf</span>(<span class="string">"%d%d%s"</span>, &amp;k, &amp;pos, s);</div><div class="line">    <span class="keyword">int</span> n = <span class="built_in">strlen</span>(s);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n &amp;&amp; i &lt; <span class="number">200000</span>; i++) &#123;</div><div class="line">        a[<span class="number">0</span>][i] = s[i] - <span class="string">'0'</span>;</div><div class="line">        b[<span class="number">0</span>][i] = <span class="number">1</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">int</span> u = <span class="number">0</span>;</div><div class="line">    <span class="keyword">while</span> (k--) &#123;</div><div class="line">        <span class="keyword">int</span> m = <span class="number">-1</span>, i = <span class="number">0</span>;</div><div class="line">        <span class="keyword">while</span> (i &lt; n &amp;&amp; i &lt; <span class="number">200000</span>) &#123;</div><div class="line">            <span class="keyword">if</span> (b[u][i] == <span class="number">0</span>) &#123;</div><div class="line">                i++;</div><div class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (b[u][i] == <span class="number">1</span>) &#123;</div><div class="line">                <span class="keyword">if</span> (m == <span class="number">-1</span>) &#123;</div><div class="line">                    m++;</div><div class="line">                    a[u^<span class="number">1</span>][m] = a[u][i+<span class="number">1</span>];</div><div class="line">                    b[u^<span class="number">1</span>][m] = a[u][i];</div><div class="line">                &#125; <span class="keyword">else</span> &#123;</div><div class="line">                    <span class="keyword">if</span> (a[u^<span class="number">1</span>][m] == a[u][i+<span class="number">1</span>]) &#123;</div><div class="line">                        b[u^<span class="number">1</span>][m] += a[u][i];</div><div class="line">                    &#125; <span class="keyword">else</span> &#123;</div><div class="line">                        m++;</div><div class="line">                        a[u^<span class="number">1</span>][m] = a[u][i+<span class="number">1</span>];</div><div class="line">                        b[u^<span class="number">1</span>][m] = a[u][i];</div><div class="line">                    &#125;</div><div class="line">                &#125;</div><div class="line">                b[u][i+<span class="number">1</span>]--;</div><div class="line">                b[u][i] = <span class="number">0</span>;</div><div class="line">            &#125; <span class="keyword">else</span> &#123;</div><div class="line">                <span class="keyword">if</span> (a[u^<span class="number">1</span>][m] == a[u][i]) &#123;</div><div class="line">                    b[u^<span class="number">1</span>][m] += a[u][i] * (b[u][i] / <span class="number">2</span>);</div><div class="line">                &#125; <span class="keyword">else</span> &#123;</div><div class="line">                    m++;</div><div class="line">                    a[u^<span class="number">1</span>][m] = a[u][i];</div><div class="line">                    b[u^<span class="number">1</span>][m] = a[u][i] * (b[u][i] / <span class="number">2</span>);</div><div class="line">                &#125;</div><div class="line">                b[u][i] %= <span class="number">2</span>;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">        n = m + <span class="number">1</span>;</div><div class="line">        u ^= <span class="number">1</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="comment">/*</span></div><div class="line"><span class="comment">    for (int i = 0; i &lt; n; i++) &#123;</span></div><div class="line"><span class="comment">        for (int j = 0; j &lt; b[u][i]; j++) &#123;</span></div><div class="line"><span class="comment">            printf("%d", a[u][i]);</span></div><div class="line"><span class="comment">        &#125;</span></div><div class="line"><span class="comment">    &#125;</span></div><div class="line"><span class="comment">    printf("\n");</span></div><div class="line"><span class="comment">    */</span></div><div class="line">    <span class="keyword">int</span> sum = <span class="number">0</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</div><div class="line">        sum += b[u][i];</div><div class="line">        <span class="keyword">if</span> (sum &gt;= pos + <span class="number">1</span>) &#123;</div><div class="line">            <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, a[u][i]);</div><div class="line">            <span class="keyword">break</span>;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/gym101173H/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/gym101173H/" itemprop="url">Gym 101173H Hangar Hurdles (最近公共祖先+并查集)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-07-02T00:00:00+08:00">
                2017-07-02
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/gym101173H/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/gym101173H/" class="cy_cmt_count" data-xid="gym101173H/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>题解参考自<a href="https://ramay7.github.io/2016/12/06/Codeforces-GYM-101173H-%E5%9B%BE%E8%BD%AC%E6%A0%91-LCA/" target="_blank" rel="external">https://ramay7.github.io/2016/12/06/Codeforces-GYM-101173H-%E5%9B%BE%E8%BD%AC%E6%A0%91-LCA/</a></p>
<p>先对每个空格求出以它为中心可以产生的最大边长的正方形，设边长为这个点的权值，把所有点按照权值从大到小排序。考虑把点生成树，而且树从底向上权值依次减小，每个点分别找它上下左右四个方向的连通块（已经加进树中）的最小权值点，把这个点的父亲赋为当前点，这样子询问就变成了求树上的LCA，判断点的连通性用并查集即可。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Node</span> &#123;</span></div><div class="line">    <span class="keyword">int</span> id, size;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">bool</span> <span class="title">cmpSize</span><span class="params">(<span class="keyword">const</span> Node &amp;a, <span class="keyword">const</span> Node &amp;b)</span> </span>&#123;</div><div class="line">    <span class="keyword">return</span> a.size &gt; b.size;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">1005</span>;</div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> M = N * N * <span class="number">2</span>;</div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> ST_SIZE = <span class="number">25</span>;</div><div class="line"><span class="keyword">int</span> n, m;</div><div class="line"><span class="keyword">char</span> maze[N][N];</div><div class="line"><span class="keyword">int</span> sum[N][N], mm[M], fat[M], depth[M], ptr[M], tree[M], position[M], st[M][ST_SIZE];</div><div class="line"><span class="keyword">int</span> treeCnt;</div><div class="line">Node p[M];</div><div class="line"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; g[M];</div><div class="line"><span class="keyword">bool</span> vis[M];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">int</span> <span class="title">getId</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y)</span> </span>&#123;</div><div class="line">    <span class="keyword">return</span> x * n + y;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">bool</span> <span class="title">isAllBlank</span><span class="params">(<span class="keyword">int</span> x1, <span class="keyword">int</span> y1, <span class="keyword">int</span> x2, <span class="keyword">int</span> y2)</span> </span>&#123;</div><div class="line">    <span class="keyword">return</span> sum[x2][y2] - sum[x1<span class="number">-1</span>][y2] - sum[x2][y1<span class="number">-1</span>] + sum[x1<span class="number">-1</span>][y1<span class="number">-1</span>] == <span class="number">0</span>;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">getSize</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y)</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> l = <span class="number">1</span>, r = min(x + <span class="number">1</span>, min(y + <span class="number">1</span>, min(n - x, n - y)));</div><div class="line">    <span class="keyword">int</span> res = <span class="number">0</span>;</div><div class="line">    <span class="keyword">while</span> (l &lt;= r) &#123;</div><div class="line">        <span class="keyword">int</span> mid = (l + r) &gt;&gt; <span class="number">1</span>;</div><div class="line">        <span class="keyword">int</span> x1 = x - mid + <span class="number">1</span>, y1 = y - mid + <span class="number">1</span>;</div><div class="line">        <span class="keyword">int</span> x2 = x + mid - <span class="number">1</span>, y2 = y + mid - <span class="number">1</span>;</div><div class="line">        <span class="keyword">if</span> (isAllBlank(x1, y1, x2, y2)) &#123;</div><div class="line">            res = mid;</div><div class="line">            l = mid + <span class="number">1</span>;</div><div class="line">        &#125; <span class="keyword">else</span> &#123;</div><div class="line">            r = mid - <span class="number">1</span>;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> max(res * <span class="number">2</span> - <span class="number">1</span>, <span class="number">0</span>);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">int</span> <span class="title">getFather</span><span class="params">(<span class="keyword">int</span> u)</span> </span>&#123;</div><div class="line">    <span class="keyword">return</span> u == fat[u] ? u : fat[u] = getFather(fat[u]);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> u, <span class="keyword">int</span> dep)</span> </span>&#123;</div><div class="line">    depth[u] = dep;</div><div class="line">    tree[++treeCnt] = u;</div><div class="line">    <span class="comment">//printf("treeCnt = %d\n", treeCnt);</span></div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; g[u].size(); i++) &#123;</div><div class="line">        dfs(g[u][i], dep + <span class="number">1</span>);</div><div class="line">        tree[++treeCnt] = u;</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">lcaInit</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= treeCnt; i++)</div><div class="line">        st[i][<span class="number">0</span>] = tree[i];</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt; ST_SIZE; j++) &#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i + (<span class="number">1</span> &lt;&lt; j) &lt;= treeCnt + <span class="number">1</span>; i++)</div><div class="line">            st[i][j] = max(st[i][j - <span class="number">1</span>], st[i + (<span class="number">1</span> &lt;&lt; (j - <span class="number">1</span>))][j - <span class="number">1</span>]);</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">lca</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r)</span> </span>&#123;</div><div class="line">    <span class="keyword">if</span> (l &gt; r) swap(l, r);</div><div class="line">    <span class="keyword">int</span> k = <span class="number">0</span>;</div><div class="line">    <span class="keyword">while</span> (l + (<span class="number">1</span> &lt;&lt; k) &lt;= r + <span class="number">1</span>) k++;</div><div class="line">    k--;</div><div class="line">    <span class="keyword">return</span> max(st[l][k], st[r + <span class="number">1</span> - (<span class="number">1</span> &lt;&lt; k)][k]);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">while</span> (<span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;n) != EOF) &#123;</div><div class="line">        m = n * n;</div><div class="line"></div><div class="line">        <span class="comment">//input maze</span></div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) </div><div class="line">            <span class="built_in">scanf</span>(<span class="string">"%s"</span>, maze[i]);</div><div class="line"></div><div class="line">        <span class="comment">//calculate sum array</span></div><div class="line">        <span class="built_in">memset</span>(sum, <span class="number">0</span>, <span class="keyword">sizeof</span>(sum));</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; n; j++) &#123;</div><div class="line">                <span class="keyword">if</span> (maze[i][j] == <span class="string">'#'</span>) sum[i][j] = <span class="number">1</span>;</div><div class="line">                <span class="keyword">if</span> (i &gt; <span class="number">0</span>) sum[i][j] += sum[i<span class="number">-1</span>][j];</div><div class="line">                <span class="keyword">if</span> (j &gt; <span class="number">0</span>) sum[i][j] += sum[i][j<span class="number">-1</span>];</div><div class="line">                <span class="keyword">if</span> (i &gt; <span class="number">0</span> &amp;&amp; j &gt; <span class="number">0</span>) sum[i][j] -= sum[i<span class="number">-1</span>][j<span class="number">-1</span>];</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; n; j++) &#123;</div><div class="line">                <span class="keyword">int</span> id = getId(i, j);</div><div class="line">                p[id].id = id;</div><div class="line">                p[id].size = getSize(i, j);</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        sort(p, p + m, cmpSize); <span class="comment">// 从大到小排序</span></div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; m; i++)</div><div class="line">            mm[p[i].id] = i;</div><div class="line"></div><div class="line">        <span class="built_in">memset</span>(vis, <span class="literal">false</span>, <span class="keyword">sizeof</span>(vis));</div><div class="line">        <span class="built_in">memset</span>(ptr, <span class="number">-1</span>, <span class="keyword">sizeof</span>(ptr));</div><div class="line">        <span class="keyword">const</span> <span class="keyword">int</span> delta[] = &#123;<span class="number">-1</span>, <span class="number">1</span>, -n, n&#125;;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; m; i++) &#123;</div><div class="line">            g[i].clear();</div><div class="line">            fat[i] = i;</div><div class="line">            vis[p[i].id] = <span class="literal">true</span>;</div><div class="line">            <span class="keyword">int</span> cid = p[i].id;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> d = <span class="number">0</span>; d &lt; <span class="number">4</span>; d++) &#123;</div><div class="line">                <span class="keyword">if</span> (cid % n == <span class="number">0</span> &amp;&amp; d == <span class="number">0</span>) <span class="keyword">continue</span>;</div><div class="line">                <span class="keyword">if</span> (cid % n == n - <span class="number">1</span> &amp;&amp; d == <span class="number">1</span>) <span class="keyword">continue</span>; </div><div class="line">                <span class="keyword">int</span> tid = cid + delta[d];</div><div class="line">                <span class="keyword">if</span> (tid &gt;= <span class="number">0</span> &amp;&amp; tid &lt; m &amp;&amp; vis[tid]) &#123;</div><div class="line">                    <span class="keyword">int</span> point = getFather(mm[tid]);</div><div class="line">                    <span class="keyword">if</span> (ptr[point] != i &amp;&amp; point != i) &#123;</div><div class="line">                        ptr[point] = i;</div><div class="line">                        g[i].push_back(point);</div><div class="line">                        fat[point] = i;</div><div class="line">                    &#125;</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        treeCnt = <span class="number">0</span>;</div><div class="line">        dfs(m - <span class="number">1</span>, <span class="number">0</span>);</div><div class="line"></div><div class="line">        <span class="built_in">memset</span>(position, <span class="number">-1</span>, <span class="keyword">sizeof</span>(position));</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= treeCnt; i++) &#123;</div><div class="line">            <span class="keyword">if</span> (position[tree[i]] == <span class="number">-1</span>) position[tree[i]] = i;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        lcaInit();</div><div class="line"></div><div class="line">        <span class="keyword">int</span> q; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;q);</div><div class="line">        <span class="keyword">while</span> (q--) &#123;</div><div class="line">            <span class="keyword">int</span> r1, c1, r2, c2;</div><div class="line">            <span class="built_in">scanf</span>(<span class="string">"%d%d%d%d"</span>, &amp;r1, &amp;c1, &amp;r2, &amp;c2);</div><div class="line">            <span class="keyword">int</span> id1 = getId(r1 - <span class="number">1</span>, c1 - <span class="number">1</span>);</div><div class="line">            <span class="keyword">int</span> id2 = getId(r2 - <span class="number">1</span>, c2 - <span class="number">1</span>);</div><div class="line">            <span class="keyword">int</span> p1 = mm[id1], p2 = mm[id2];</div><div class="line">            <span class="keyword">int</span> f = lca(position[p1], position[p2]);</div><div class="line">            <span class="comment">//printf("%d %d\n", f / n + 1, f % n + 1);</span></div><div class="line">            <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, p[f].size);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/gym101173F/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/gym101173F/" itemprop="url">Gym 101173F Free Figurines (模拟)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-07-02T00:00:00+08:00">
                2017-07-02
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/gym101173F/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/gym101173F/" class="cy_cmt_count" data-xid="gym101173F/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>直接模拟一下拆娃娃的操作即可。其中需要分情况讨论。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">100005</span>;</div><div class="line"><span class="keyword">int</span> n, ans;</div><div class="line"><span class="keyword">int</span> fat[N][<span class="number">2</span>], son[N][<span class="number">2</span>];</div><div class="line"><span class="built_in">queue</span>&lt;<span class="keyword">int</span>&gt; leaf;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">openFigurine</span><span class="params">(<span class="keyword">int</span> u)</span> </span>&#123;</div><div class="line">    <span class="keyword">if</span> (u != <span class="number">0</span>) &#123;</div><div class="line">        <span class="keyword">int</span> s = son[u][<span class="number">0</span>];</div><div class="line">        <span class="keyword">int</span> f = fat[u][<span class="number">0</span>];</div><div class="line">        <span class="keyword">if</span> (s != <span class="number">0</span>) &#123;</div><div class="line">            son[u][<span class="number">0</span>] = <span class="number">0</span>;</div><div class="line">            fat[s][<span class="number">0</span>] = <span class="number">0</span>;</div><div class="line">            ans++;</div><div class="line">        &#125;</div><div class="line">        openFigurine(f);</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">while</span> (<span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;n) != EOF) &#123;</div><div class="line">        <span class="comment">// initialize</span></div><div class="line">        <span class="built_in">memset</span>(fat, <span class="number">0</span>, <span class="keyword">sizeof</span>(fat));</div><div class="line">        <span class="built_in">memset</span>(son, <span class="number">0</span>, <span class="keyword">sizeof</span>(son));</div><div class="line">        <span class="keyword">while</span> (!leaf.empty()) leaf.pop();</div><div class="line">        ans = <span class="number">0</span>;</div><div class="line"></div><div class="line">        <span class="comment">// input</span></div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">            <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;fat[i][<span class="number">0</span>]);</div><div class="line">            <span class="keyword">if</span> (fat[i][<span class="number">0</span>] != <span class="number">0</span>) son[fat[i][<span class="number">0</span>]][<span class="number">0</span>] = i;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">            <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;fat[i][<span class="number">1</span>]);</div><div class="line">            <span class="keyword">if</span> (fat[i][<span class="number">1</span>] != <span class="number">0</span>) son[fat[i][<span class="number">1</span>]][<span class="number">1</span>] = i;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="comment">// add leaf nodes</span></div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">            <span class="keyword">if</span> (son[i][<span class="number">1</span>] == <span class="number">0</span>) leaf.push(i);</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="comment">// main</span></div><div class="line">        <span class="keyword">while</span> (!leaf.empty()) &#123;</div><div class="line">            <span class="keyword">int</span> u = leaf.front(); leaf.pop();</div><div class="line">            <span class="keyword">if</span> (son[u][<span class="number">0</span>] == <span class="number">0</span>) &#123; <span class="comment">// if u doesn't has son node originally</span></div><div class="line">                <span class="keyword">if</span> (fat[u][<span class="number">1</span>] == <span class="number">0</span> &amp;&amp; fat[u][<span class="number">0</span>] == <span class="number">0</span>) &#123; <span class="comment">// if u doesn't has father node originally and now</span></div><div class="line">                    <span class="comment">// do nothing</span></div><div class="line">                &#125; <span class="keyword">else</span> <span class="keyword">if</span> (fat[u][<span class="number">1</span>] == fat[u][<span class="number">0</span>]) &#123; <span class="comment">// if the node of u doesn't change</span></div><div class="line">                    <span class="keyword">int</span> f = fat[u][<span class="number">1</span>];</div><div class="line">                    leaf.push(f);</div><div class="line">                    son[f][<span class="number">0</span>] = son[f][<span class="number">1</span>] = <span class="number">0</span>;</div><div class="line">                &#125; <span class="keyword">else</span> &#123;</div><div class="line">                    openFigurine(fat[u][<span class="number">0</span>]);</div><div class="line">                    openFigurine(fat[u][<span class="number">1</span>]);</div><div class="line">                    <span class="keyword">int</span> f = fat[u][<span class="number">1</span>];</div><div class="line">                    <span class="keyword">if</span> (f != <span class="number">0</span>) &#123;</div><div class="line">                        leaf.push(f);</div><div class="line">                        son[f][<span class="number">0</span>] = son[f][<span class="number">1</span>] = <span class="number">0</span>;</div><div class="line">                        ans++;</div><div class="line">                    &#125;</div><div class="line">                &#125;</div><div class="line">            &#125; <span class="keyword">else</span> &#123;</div><div class="line">                openFigurine(u);</div><div class="line">                openFigurine(fat[u][<span class="number">1</span>]);</div><div class="line">                <span class="keyword">int</span> f = fat[u][<span class="number">1</span>];</div><div class="line">                <span class="keyword">if</span> (f != <span class="number">0</span>) &#123;</div><div class="line">                    leaf.push(f);</div><div class="line">                    son[f][<span class="number">0</span>] = son[f][<span class="number">1</span>] = <span class="number">0</span>;</div><div class="line">                    ans++;</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">        <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, ans);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <a class="extend prev" rel="prev" href="/page/4/"><i class="fa fa-angle-left"></i></a><a class="page-number" href="/">1</a><span class="space">&hellip;</span><a class="page-number" href="/page/4/">4</a><span class="page-number current">5</span><a class="page-number" href="/page/6/">6</a><span class="space">&hellip;</span><a class="page-number" href="/page/11/">11</a><a class="extend next" rel="next" href="/page/6/"><i class="fa fa-angle-right"></i></a>
  </nav>



          </div>
          


          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="/img/head.png"
                alt="cayun" />
            
              <p class="site-author-name" itemprop="name">cayun</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">102</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">3</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">79</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          <div class="links-of-author motion-element">
            
              
                <span class="links-of-author-item">
                  <a href="https://github.com/comeacrossyun" target="_blank" title="GitHub">
                    
                      <i class="fa fa-fw fa-github"></i>GitHub</a>
                </span>
              
                <span class="links-of-author-item">
                  <a href="mailto:comeacrossyun@gmail.com" target="_blank" title="E-Mail">
                    
                      <i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                </span>
              
            
          </div>

          
          

          
          

          

        </div>
      </section>

      

      
        <div class="back-to-top">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2017</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">cayun</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Pisces</a></div>




        







        
      </div>
    </footer>

    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.3"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.3"></script>



  

  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.3"></script>



  


  




	





  





  




  
    <script id="cy_cmt_num" src="https://changyan.sohu.com/upload/plugins/plugins.list.count.js?clientId=cyt6VLWhj"></script>
  









  





  

  
<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script>


  
  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.bootcss.com/mathjax/2.7.1/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  

  

</body>
</html>
